package graph.impl;

import graph.core.IEdge;
import graph.core.IGraph;
import graph.core.IIterator;
import graph.core.IList;
import graph.core.IPosition;
import graph.core.IVertex;
import graph.util.DLinkedList;

/**
 * Adjacency List implementation of the Graph data structure.
 * 
 * Each vertex maintains a list containing all its connected edges.
 * This implementation is suitable for sparse graphs (number of edges much less
 * than |V|²).
 * Time complexity:
 * - areAdjacent: O(deg(v)), where deg(v) is the degree of vertex v
 * - incidentEdges: O(1)
 * - insertEdge/removeEdge: O(1)
 */
public class AdjacencyListGraph<V, E> implements IGraph<V, E> {
    /**
     * Inner class to represent a vertex in an adjacency list graph implementation
     */
    private class ALVertex implements IVertex<V> {
        // reference to a node in the vertex list
        IPosition<IVertex<V>> node;

        // element stored in this vertex
        V element;

        // list storing all edges connected to this vertex
        IList<IEdge<E>> incidentEdges;

        public ALVertex(V element) {
            this.element = element;
            this.incidentEdges = new DLinkedList<IEdge<E>>();
        }

        @Override
        public V element() {
            return element;
        }

        public String toString() {
            return element.toString();
        }
    }

    /**
     * Inner class to represent an edge in an adjacency list graph implementation
     */
    private class ALEdge implements IEdge<E> {
        // reference to a node in the edge list
        IPosition<IEdge<E>> node;

        // element stored in this edge
        E element;

        // the start and end vertices that this edge connects
        ALVertex start, end;

        // positions in the adjacency lists of the start and end vertices
        IPosition<IEdge<E>> startPos, endPos;

        public ALEdge(ALVertex start, ALVertex end, E element) {
            this.start = start;
            this.end = end;
            this.element = element;
        }

        @Override
        public E element() {
            return element;
        }

        public String toString() {
            return element.toString();
        }
    }

    // vertex list
    private IList<IVertex<V>> vertices;

    // edge list
    private IList<IEdge<E>> edges;

    /**
     * Constructor
     */
    public AdjacencyListGraph() {
        vertices = new DLinkedList<IVertex<V>>();
        edges = new DLinkedList<IEdge<E>>();
    }

    @Override
    public IVertex<V>[] endVertices(IEdge<E> e) {
        ALEdge edge = (ALEdge) e;

        @SuppressWarnings("unchecked")
        IVertex<V>[] endpoints = new IVertex[2];

        endpoints[0] = edge.start;
        endpoints[1] = edge.end;

        return endpoints;
    }

    @Override
    public IVertex<V> opposite(IVertex<V> v, IEdge<E> e) {
        ALEdge edge = (ALEdge) e;

        if (edge.start.equals(v)) {
            return edge.end;
        } else if (edge.end.equals(v)) {
            return edge.start;
        }

        throw new RuntimeException("Error: cannot find opposite vertex.");
    }

    @Override
    public boolean areAdjacent(IVertex<V> v, IVertex<V> w) {
        // get all incident edges of the first vertex
        ALVertex vertex = (ALVertex) v;
        IIterator<IEdge<E>> it = vertex.incidentEdges.iterator();

        // check if any edge connects to w
        while (it.hasNext()) {
            ALEdge edge = (ALEdge) it.next();
            if (edge.start.equals(w) || edge.end.equals(w)) {
                return true;
            }
        }

        return false;
    }

    @Override
    public V replace(IVertex<V> v, V x) {
        ALVertex vertex = (ALVertex) v;
        V temp = vertex.element;
        vertex.element = x;
        return temp;
    }

    @Override
    public E replace(IEdge<E> e, E x) {
        ALEdge edge = (ALEdge) e;
        E temp = edge.element;
        edge.element = x;
        return temp;
    }

    @Override
    public IVertex<V> insertVertex(V v) {
        if (v == null) {
            throw new IllegalArgumentException("顶点元素不能为空");
        }
        ALVertex vertex = new ALVertex(v);
        IPosition<IVertex<V>> node = vertices.insertLast(vertex);
        vertex.node = node;
        return vertex;
    }

    @Override
    public IEdge<E> insertEdge(IVertex<V> v, IVertex<V> w, E o) {
        if (v == null || w == null) {
            throw new IllegalArgumentException("Vertices cannot be null");
        }

        // 尝试进行类型转换
        ALVertex start, end;
        try {
            start = (ALVertex) v;
            end = (ALVertex) w;
        } catch (ClassCastException e) {
            throw new IllegalArgumentException("Vertex type mismatch");
        }

        // check if vertices are already adjacent or if it's a self-loop
        if (areAdjacent(v, w) || v.equals(w)) {
            throw new IllegalArgumentException("Vertices are already adjacent or trying to create a self-loop");
        }

        // create new edge
        ALEdge edge = new ALEdge(start, end, o);

        // add the edge to the edge list
        IPosition<IEdge<E>> node = edges.insertLast(edge);
        edge.node = node;

        // add the edge to the adjacency lists of the start and end vertices
        edge.startPos = start.incidentEdges.insertLast(edge);
        edge.endPos = end.incidentEdges.insertLast(edge);

        return edge;
    }

    @Override
    public V removeVertex(IVertex<V> v) {
        ALVertex vertex = (ALVertex) v;

        // remove all edges incident to this vertex
        while (!vertex.incidentEdges.isEmpty()) {
            ALEdge edge = (ALEdge) vertex.incidentEdges.first().element();
            removeEdge(edge);
        }

        // remove the vertex from the vertex list
        vertices.remove(vertex.node);

        return vertex.element;
    }

    @Override
    public E removeEdge(IEdge<E> e) {
        ALEdge edge = (ALEdge) e;

        // remove the edge from the adjacency lists of the start and end vertices
        edge.start.incidentEdges.remove(edge.startPos);
        edge.end.incidentEdges.remove(edge.endPos);

        // remove the edge from the edge list
        edges.remove(edge.node);

        return edge.element;
    }

    @Override
    public IIterator<IEdge<E>> incidentEdges(IVertex<V> v) {
        ALVertex vertex = (ALVertex) v;
        return vertex.incidentEdges.iterator();
    }

    @Override
    public IIterator<IVertex<V>> vertices() {
        return vertices.iterator();
    }

    @Override
    public IIterator<IEdge<E>> edges() {
        return edges.iterator();
    }
}